package Leetcode第二期;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author : K k
 * @date : 14:41 2020/9/20
 */
public class 腐烂的橘子_994 {

    public int orangesRotting(int[][] grid) {
        int N = grid.length;
        int M = grid[0].length;
        int count = 0;//新鲜橘子的个数
        int minute = 0;
        Queue<int[]> queue = new LinkedList<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (grid[i][j] == 1) {
                    count++;
                }
                if (grid[i][j] == 2) {
                    queue.offer(new int[]{i, j});
                }
            }
        }
        while (count > 0 && !queue.isEmpty()) {
            minute++;
            int n = queue.size();
            for (int k = 0; k < n; k++) {
                int[] position = queue.poll();
                int i = position[0];
                int j = position[1];
                //四个方向
                if (i - 1 >= 0 && grid[i][j] == 1) {
                    grid[i - 1][j] = 2;//感染
                    count--;
                    queue.offer(new int[]{i - 1, j});
                }
                if (j - 1 >= 0 && grid[i][j - 1] == 1) {
                    grid[i][j - 1] = 2;//感染
                    count--;
                    queue.offer(new int[]{i, j - 1});
                }
                if (i + 1 <= N && grid[i][j] == 1) {
                    grid[i + 1][j] = 2;//感染
                    count--;
                    queue.offer(new int[]{i + 1, j});
                }
                if (j + 1 <= M && grid[i][j + 1] == 1) {
                    grid[i][j + 1] = 2;//感染
                    count--;
                    queue.offer(new int[]{i, j + 1});
                }
            }
        }
        if (count != 0) {
            return -1;
        } else {
            return minute;
        }
    }

}
